Skok w bok

Limit pamięci: 32 MB

Plansza do gry „Skok w bok” jest nieskończoną taśmą pól, nieograniczoną zarówno w lewo jak i w prawo. Na polach planszy stoją pionki. Ich liczba jest skończona. Na jednym polu może stać równocześnie wiele pionków. Zakładamy, że pierwsze od lewej pole, na którym jest przynajmniej jeden pionek, ma numer . Pola na prawo od niego są oznaczone kolejno liczbami naturalnymi , a pola w lewo liczbami ujemnymi: . Ustawienie pionków na taśmie, które będziemy także nazywać konfiguracją, można opisać w ten sposób, że dla każdego pola, na którym jest co najmniej jeden pionek, podaje się numer pola i liczbę pionków na tym polu.

Są dwa rodzaje ruchów, zmieniających konfiguracje: skok w prawo i skok w lewo. Skok w prawo polega na zabraniu po jednym pionku z wybranych dwóch sąsiednich pól o numerach oraz i dodaniu jednego pionka na polu . Skok w lewo: zabieramy jeden pionek z pola , a dodajemy po jednym na polach i .

Mówimy, że konfiguracja jest końcowa, jeśli na dowolnych dwóch sąsiednich polach znajduje się co najwyżej jeden pionek. Dla każdej konfiguracji istnieje dokładnie jedna konfiguracja końcowa, którą można z niej otrzymać w wyniku skończonej liczby skoków w prawo lub w lewo.

Zadanie

Ułóż program, który:

• wczytuje opis konfiguracji początkowej ze standardowego wejścia,
• znajduje konfigurację końcową, do jakiej można doprowadzić daną konfigurację początkową i zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia . Jest to liczba niepustych pól danej konfiguracji początkowej, .

W każdym z kolejnych wierszy znajduje się opis jednego niepustego pola konfiguracji początkowej w postaci pary liczb całkowitych oddzielonych odstępem. Pierwsza liczba to numer pola, a druga — to liczba pionków na tym polu. Te opisy są uporządkowane rosnąco według numerów pól. Największy numer pola nie przekracza , a liczba pionków na żadnym polu nie przekracza .

Wyjście

W pierwszym wierszu standardowego wyjścia należy zapisać konfigurację końcową, do której można przekształcić daną konfigurację początkową — numery kolejnych niepustych pól konfiguracji końcowej. Numery te powinny być uporządkowane rosnąco. Liczby w wierszu powinny być pooddzielane pojedynczym odstępem.

Przykład

Dla danych wejściowych:

2
0 5
3 3

poprawną odpowiedzią jest:

-4 -1 1 3 5 

Autor zadania: Bogdan S. Chlebus.